/*
1376.通知所有员工所需的时间
https://leetcode.cn/problems/time-needed-to-inform-all-employees/
2024/10/14 中等
*/
#include <vector>
#include <unordered_map>
#include <string>
#include <iostream>
using namespace std;
class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager,
                     vector<int>& informTime) {
        //if (n == 1 || informTime.size() == 1 || manager.size() == 1)
          //  return {0};
        vector<vector<int>> adjList(n);
        for (int i = 0; i < n; ++i) {
            if (manager[i] != -1) {
                adjList[manager[i]].push_back(i);
            }
        }
        return dfs(headID, adjList, informTime);
    }
    int dfs(int node, const vector<vector<int>>& adjList,
            const vector<int>& informTime) {
        int maxTime = 0;
        for (int child : adjList[node]) {
            maxTime = max(maxTime, dfs(child, adjList, informTime));
        }
        return maxTime + informTime[node];
    }
};
// 测试用例
int main() {
    Solution solution;
    int n1 = 7;
    vector<vector<int>> edges1 = {{0, 1}, {0, 2}, {1, 4}, {1, 5}, {2, 3}, {2, 6}};
    string labels1 = "abaedcd";
    vector<int> result1 = solution.countSubTrees(n1, edges1, labels1);
    for (int i : result1) cout << i << " ";  // 输出：2 1 1 1 1 1 1
    cout << endl;

    int n2 = 4;
    vector<vector<int>> edges2 = {{0, 1}, {1, 2}, {0, 3}};
    string labels2 = "bbbb";
    vector<int> result2 = solution.countSubTrees(n2, edges2, labels2);
    for (int i : result2) cout << i << " ";  // 输出：4 2 1 1
    cout << endl;

    return 0;
}